package com.wu.leetcode.leetcode79;

import java.util.ArrayList;

/**
 * Leetcode79-单词搜索
 *
 * @author lynn
 * @date 2020/10/30 - 10:51
 */
public class Solution {
    public static boolean exist(char[][] board, String word) {
        int row = board.length;
        int col = board[0].length;
        boolean[][] isVisited = new boolean[row][col];

        char[] chars = word.toCharArray();
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (dfs(board, isVisited, chars, 0, i, j)) {
                    return true;
                }
            }
        }
        return false;
    }

    private static boolean dfs(char[][] board, boolean[][] isVisited, char[] chars, int index, int row, int col) {
        if (row < 0 || col < 0 || row >= board.length || col >= board[0].length || board[row][col] != chars[index] || isVisited[row][col]) {
            return false;
        }
        if (index + 1 == chars.length) {
            return true;
        }
        isVisited[row][col] = true;
        if (dfs(board, isVisited, chars, index + 1, row + 1, col) ||
                dfs(board, isVisited, chars, index + 1, row - 1, col) ||
                dfs(board, isVisited, chars, index + 1, row, col + 1) ||
                dfs(board, isVisited, chars, index + 1, row, col - 1)) {
            return true;
        }
        isVisited[row][col] = false;
        return false;
    }

    public static void main(String[] args) {
        char[][] chars = new char[][]{
                {'A', 'B', 'C', 'E'},
                {'S', 'F', 'C', 'S'},
                {'A', 'D', 'E', 'E'}};

        boolean abcced = exist(chars, new String("ABCB"));
        System.out.println(abcced);
    }
}
